﻿#pragma once
template<class K>
struct BTreeNode 
{
	BTreeNode(const K& key = K()):_left(nullptr),_right(nullptr),_key(key)
	{	}
	BTreeNode<K>* _left;
	BTreeNode<K>* _right;
	K _key;
};

template<class K>
class BSTree
{
	typedef BTreeNode<K> Node;
public:
	BSTree():_root(nullptr)
	{ }
	//void _deleteBSTree(Node* root)
	//{
	//	if (_root == nullptr)
	//	{
	//		return;
	//	}
	//	_deleteBSTree(_root->_left);
	//	_deleteBSTree(_root->_right);
	//	delete _root;
	//}
	//~BSTree()
	//{
	//	_deleteBSTree(_root);
	//}
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
		}
		Node* cur = _root;
		Node* prev = nullptr;
		int flag = 1;
		while (cur)
		{
			prev = cur;
			if (cur->_key < key)
			{
				cur = cur->_right;
				flag = 1;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
				flag = 0;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(key);
		if (flag)
		{
			prev->_right = cur; 
		}
		else
		{
			prev->_left = cur;
		}
		return true;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}
	 Node* Find(const K& key)const
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				return cur;
		}
		return nullptr;
	}
	 bool Erase(const K& key)
	 {
		 //首先判断是否为空，为空返回假
		 if (_root == nullptr)return false;
		 //再去查找要删除元素
		 Node* cur = _root;
		 Node* prev = nullptr;
		 while (cur)
		 {
			 if (cur->_key < key)
			 {
				 prev = cur;
				 cur = cur->_right;
			 }
			 else if (cur->_key > key)
			 {
				 prev = cur;
				 cur = cur->_left;
			 }
			 else
			 {
				 break;
			 }
		 }
		 //没找到则cur==nullptr返回false
		 if (cur == nullptr)return false;
		 //3种情况
			// 1.当前节点为叶子节点
			// 2.当前节点只有一个子节点
			// 3.当前节点右两个子节点
				//内部2种情况
					// 1.删除节点为根节点
					// 2.删除节点不为根节点
		 if (cur->_left == nullptr && cur->_right == nullptr)
		 {
			 if (prev == nullptr)_root = nullptr;
			 else {
				 if (prev->_left == cur)prev->_left = nullptr;
				 else prev->_right = nullptr;
			 }
			 delete cur;
		 }
		 else if (cur->_left == nullptr || cur->_right == nullptr)
		 {
			 Node* child = cur->_left != nullptr ? cur->_left : cur->_right;
			 if (prev == nullptr)
			 {
				 _root = child;
			 }
			 else
			 {
				 if (prev->_left == cur)prev->_left = child;
				 else prev->_right = child;
			 }
			 delete cur;
		 }
		 else
		 {	
			  //找到要删除节点右子树的最小值作为被交换点
			 Node* rMin = cur->_right;//最小值节点起始点为当前位置右子树的根
			 Node* rMinPrev = cur;//最小值节点的父节点就应为当前位置
			 //直到最小节点的左节点为空则找到
			 while(rMin->_left)
			{
		 	 rMinPrev = rMin;
		 	 rMin=rMin->_left;//一直向左找
			}
			cur->_key = rMin->_key;//被删除位置值替换为右子树最小值
			 if (rMin == rMinPrev->_left) rMinPrev->_left = rMin->_right;
		     else rMinPrev->_right = rMin->_right;
			//删除被替换过的右子树最小节点
			delete rMin;
		 }

		 ////找到以后先判断
		 //if (cur->_left == nullptr&& prev != nullptr)
		 //{
			// if (cur == prev->_right)
			// {
			//	 prev->_right = cur->_right;
			// }
			// else
			// {
			//	 prev->_left = cur->_right;
			// }
			// delete cur;
		 //}
		 //else if (cur->_right == nullptr&& prev != nullptr)
		 //{
			// if (cur == prev->_left)
			// {
			//	 prev->_left = cur->_left;
			// }
			// else
			// {
			//	 prev->_right = cur->_left;
			// }
			// delete cur;
		 //}
		 //else if (cur->_left == nullptr && cur->_right == nullptr && prev == nullptr)
		 //{
			// delete cur;
			// _root = nullptr;
		 //}
		 //else
		 //{
			//
			// //找到要删除节点右子树的最小值作为被交换点
			// Node* rMin = cur->_right;//最小值节点起始点为当前位置右子树的根
			// Node* rMinPrev = cur;//最小值节点的父节点就应为当前位置
			// //直到最小节点的左节点为空则找到
			// while(rMin->_left)
			// {
			//	 rMinPrev = rMin;
			//	 rMin=rMin->_left;//一直向左找
			// }
			// cur->_key = rMin->_key;//被删除位置值替换为右子树最小值
			// //判断右子树被替换点在父节点左边还是右边
			// //并将右子树最小节点自己的右子树接回父节点正确位置 
			// if (rMin == rMinPrev->_left)
			// {
			//	 rMinPrev->_left = rMin->_right;
			// }
			// else rMinPrev->_right = rMin->_right;
			// //删除被替换过的右子树最小节点
			// delete rMin;
		 //}
		 return true;
	 }
private:
	Node* _root=nullptr;
};

void TestBSTree1()
{
	cout << "TestBSTree1" << endl;
	BSTree<int> bst1;
	int a[] = { 5,3,4,1,7,8,2,6,0,9 };
	for (auto e : a)
	{
		bst1.Insert(e);
	}
	
	bst1.InOrder();
	int a2[] = { 5,3,4,1,7,11,8,2,6,0,9};
	BTreeNode<int>* ret = bst1.Find(5);
	cout << ret->_key << endl;
	for (auto e : a2)
	{
		bst1.Erase(e);
		bst1.InOrder();
	}
	

	cout << "TestBSTree1" << endl;
}